package 算法.排序;

import java.util.Arrays;


public class paixu{

    public static void main(String[] args) {
        System.out.println("======");

    }
    public static void swap(int[] arr,int i,int j)
    {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

    public static void out(int[] arr)
    {
        for (int i=0;i<arr.length;i++)
        {
            System.out.print(arr[i]+" ");
        }
    }

}



/**
 * 1.冒泡排序
 */
class maopao  {

    public static void main(String args[]) {
        int array[]={1,2,4,3,9,7,8,6,5};
        for (int i=0;i<array.length;i++)
        {
            for (int j=0;j<array.length-i-1;j++)
            {
                if (array[j]>array[j+1])
                {
                    paixu.swap(array,j,j+1);
                }
            }
        }
            System.out.println(Arrays.toString(array));
    }
}

/**
 * 2.选择排序
 */

class xuanzepaixu{
    public static void main(String[] args) {
    int minIndex=0;
    int temp=0;
    int array[]={1,2,4,3,9,7,8,6,5};
    for(int i=0;i<array.length;i++)
    {
        minIndex=i;
        for (int j=i;j<array.length;j++)
        {
            if (array[j]<array[minIndex])
            {
              minIndex=j;
            }
        }
        paixu.swap(array,minIndex,i);
    }
       paixu.out(array);
    }
}


/**
 * 3.插入排序1
 */
class  charupaixu{
    public static void main(String[] args) {
        int array[]={1,2,4,3,9,7,8,6,5};
        for (int i=0;i<array.length-1;i++)
        {
            for (int j=i;j>0;j--)
            {
                if (array[j+1]<array[j])
                {
                    int temp=array[j+1];
                    array[j+1]=array[j];
                    array[j]=temp;
                }
            }
        }
         for (int i=0;i<array.length;i++)
            {
                System.out.print(array[i]);
            }
    }
}

/**
 * 3.1插入排序2
 */
class charupaixu2{
    public static void main(String[] args) {
        int array[]={1,2,4,3,9,7,8,6,5};
        int index=0;
        int current=0;
        for (int i=1;i<array.length;i++)
        {
            index=i-1;    //左边的元素是排好序的
            current =array[i];   //表示当前取到的元素
            while (index>=0&&array[index]>current)  //如果左边的元素比取到的元素大则右移
            {
                array[index+1]=array[index];
                index--;
            }
            array[index+1]=current;//直到取到的元素比后面的元素小（或相等），将取到的元素插到已经排好序元素的后面
        }
        for (int i=0;i< array.length;i++)
            System.out.print(array[i]+" ");
    }
}

/**
 * 4.希尔排序
 */
class xierpaixu{
    public static void main(String[] args) {
        int array[] = {1, 2, 4, 3, 9, 7, 8, 6, 5};
        int size = array.length/2;  //希尔排序步长选取没有定论
        while (size>=1)
        {
            for (int i=0;i<array.length;i++)
            {
                for (int j=i;j+size<array.length;j+=size)
                {
                    if (array[j]>array[j+size])
                    {
                        int temp=array[j];
                        array[j]=array[j+size];
                        array[j+size]=temp;
                    }
                }
            }
            size=size/2;
        }
        for (int i=0;i<array.length;i++)
        {
            System.out.print(array[i]+" ");
        }
    }
}


/***
 * 5.归并排序
 * 该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；
 * 即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2路归并
 */

class guibingpaixu
{
    public static void main(String[] args)
    {
        int[] nums={1,4,7,8,3,6,9};
        sort(nums,0,nums.length-1);
        paixu.out(nums);

    }
    public static void sort(int[] arr,int left,int right)
    {
        if (left==right)
            return;
        //分成两半
        int mid=left+(right-left)/2;
        //对左边排序
        sort(arr,left,mid);
        //右边排序
        sort(arr,mid+1,right);

        merge(arr,left,mid+1,right);
    }
    static void merge(int[] arr,int left,int right,int rightBound)
    {
        int mid=right-1;
        int[] temp=new int[right-left+1];
        int i=left;
        int j=right;
        int k=0;  //k指向临时数组
        while (i<=mid && j<rightBound)
        {
            if (arr[i]<arr[j])
            {
                temp[k]=arr[i];
                i++;
                k++;
            }
            else
            {
                temp[k]=arr[j];
                j++;
                k++;
            }
        }
        while (i<=mid) temp[k++]=arr[i++];
        while (j<=rightBound) temp[k++]=arr[j++];
       for (int m=0;m<temp.length;m++)
       {
           arr[left+m]=temp[m];
       }
    }
}

/**
 * 6.快速排序
 * 通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另外一部分的关键字小
 *则可分别对这两部分记录进行排序，以达到整个序列有序。
 * 快速排序使用分治法把一个串分为两个子串
 * 1.从数列中挑出一个元素，称为基准（“pivot”）
 * 2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素都比基准值大的摆在基准的后面
 * 在这个分区退出之后，该基准就处于数列的中间位置，这个称为分区操作；
 * 3.递归地把小于基准值元素的子数列和大于基准值元素的子数列排序
 */

class  kuaisupaixu{
    public static void main(String[] args)
    {
        int array[] = {1, 2, 4, 3, 9, 7, 8, 6, 5};
        quicksort(array,0,array.length-1);
        for (int i=0;i<array.length;i++)
        {
            System.out.print(array[i]+"");
        }
    }

    private static void quicksort(int[] arr, int l, int r)
    {
        if (l>=r) return;
        int p=parttion(arr,l,r);        //找到中间位置
        quicksort(arr,l,p-1);
        quicksort(arr,p+1,r);

    }
    private static int parttion(int[] arr,int l,int r)
    {
        int v=arr[l];                   //取出第一个元素
        int j=l;                        //j表示小于第一个元素和大于第一个元素的分界点
        for (int i=l+1;i<=r;i++)
        {
            //将所有小于第一个元素的值的元素全部放到它的左边
            if (arr[i]<v)        //如果当前元素小于V，则交换
            {
              int temp=arr[j+1];
              arr[j+1]=arr[i];
              arr[i]=temp;
                j++;
            }
        }
        int temp2=arr[l];  //将第一个元素和中间的元素交换
        arr[l]=arr[j];
        arr[j]=temp2;
        return  j;
    }
}
/**
 * 6.1 快速排序2
 */
class quicksort2{

    public static void main(String[] args) {
        int array[] = {1, 2, 4, 3, 9, 7, 8, 6, 5};
        quicksort(array,0,array.length-1);
        paixu.out(array);
    }

    private static void quicksort(int[] array, int low, int high) {
        if (low>=high) return;
        int index=getIndex(array,low,high);
        quicksort(array,low,index-1);
        quicksort(array,index+1,high);
    }
    private static int getIndex(int[] array,int low,int high)
    {
        int temp=array[low];   //基准数据
        while (low<high)
        {
            //当队尾的元素大于等于基准数据时，向前挪动high指针
            while (low<high && array[high]>=temp)
            {
                high--;
            }
            //如果队尾元素小于tmp,需要将其赋值给low
            array[low]=array[high];

            //当队首元素小于等于tmp时，向前挪动指针
            while (low<high && array[low]<=temp)
            {
                low++;
            }
            //如果对首元素大于tmp时，将其赋值给high
            array[high]=array[low];
        }
        array[low]=temp;
        return low; //返回tmp的正确位置
    }

}

/**
 * 7.堆排序
 * 堆排序是指利用堆这种数据结构所设计的一种排序算法。
 * 最大堆要求节点的元素都要不小于其孩子节点，最小堆要求节点元素都不大于其左右孩子
 * 那么出于最大堆的根结点的元素一定是这个队中的最大值
 */
class  heapsort {

    public static void main(String[] args) {
        int A[] = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51};
        HeapSort(A, A.length);
        System.out.println(Arrays.toString(A));
    }

    public static void swap(int A[], int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

    public static void Heapify(int A[], int i, int size)  //从A[i]向下进行堆调整
    {
        int left_child = 2 * i + 1;       //左孩子索引
        int right_child = 2 * i + 2;      //右孩子索引
        int max = i;                      //选出当前结点与其左右孩子三者之中最大值
        if (left_child < size && A[left_child] > A[max]) {
            max = left_child;
        }
        if (right_child < size && A[right_child] > A[max]) {
            max = right_child;
        }
        if (max != i) {
            swap(A, i, max);          //把当前结点和它的最大直接子节点进行交换
            Heapify(A, max, size);     //递归调用，继续从当前结点向下进行堆调整
        }
    }

    public static int BuildHeap(int A[], int n)        //建堆，时间复杂度O（n）
    {
        int heap_size = n;
        for (int i = heap_size / 2 - 1; i >= 0; i--) {
            Heapify(A, i, heap_size);
        }
        return heap_size;
    }

    private static void HeapSort(int[] A, int length) {
        int heap_size = BuildHeap(A, length);
        while (heap_size > 1)            //堆（无序区）元素个数大于1，未完成排序
        {
            //将堆元素和堆的最后一个元素互换，并从堆中去掉最后一个元素
            //此操作很可能把后面元素稳定性打乱，所以堆排序是不稳定的排序算法
            swap(A, 0, --heap_size);
            Heapify(A, 0, heap_size);  //从新的堆顶元素向下进行堆排序，时间复杂度O（logn）
        }
    }
}

/**
 * 7.1堆排序
 */
class heapsort1{
    public static void main(String[] args) {
        int[] arr={9,8,7,6,5,4,3,2,1};
        heapsort2(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void heapsort2(int[] arr) {
        //1.构建大顶堆
        for (int i=arr.length/2-1;i>=0;i--)
        {
            //从第一个非叶结点自下至上，从右至左调整结构
            adjustheap(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素和末尾元素
        for (int j=arr.length-1;j>0;j--)
        {
            swap(arr,0,j);
            adjustheap(arr,0,j);//重新对堆进行排序
        }

    }

    private static void adjustheap(int[] arr, int i, int length) {
        int temp=arr[i]; //先取出当前元素i;
        for (int k=i*2+1;k<length;k=k*2+1)   //从i节点的左子结点开始，也就是2i+1处开始
        {
            if (k+1<length && arr[k]<arr[k+1])
            {//如果左子节点小于右子结点，k指向右子节点
                k++;
            }
            if (arr[k]>temp)   //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
            {
                arr[i]=arr[k];
                i=k;
            }
            else {
                break;
            }
        }
        arr[i]=temp;//将temp值放在最终位置上
    }

    /**
     * 交换元素
     * @param arr
     * @param i
     * @param j
     */
    private static void swap(int[] arr, int i, int j)
    {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }



}









